package com.tgy.algorithm.base._图;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

public class _构建图 {

    /**
     *
     *
     *
     *  [
     *      [0,1,10],
     *      [0,2,4],
     *      [1,2,2],
     *      [2,3,3],
     *      [3,1,3],
     *      [2,1,3],
     *  ]
     *
     * @param matrix
     * @return
     */
    public static Graph createGraph(Integer[][] matrix) {

        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer[] info = matrix[i];
            Integer fromValue = info[0];
            Integer toValue = info[1];
            Integer weight = info[2];
            if (!graph.nodes.containsKey(fromValue)) {
                graph.nodes.put(fromValue, new Node(fromValue));
            }
            if (!graph.nodes.containsKey(toValue)) {
                graph.nodes.put(toValue, new Node(toValue));
            }
            Node from = graph.nodes.get(fromValue);
            Node to = graph.nodes.get(toValue);
            from.out++;
            from.nexts.add(to);
            to.in++;
            Edge edge = new Edge(weight,from,to);
            from.edges.add(edge);
            graph.edges.add(edge);
        }

        return graph;
    }

    /**
     * 广度优先遍历
     * breadth first search
     * @param node
     */
    public static void bfs(Node node) {
        LinkedList<Node> queue = new LinkedList<>();

        HashSet<Node> visitSet = new HashSet<>();
        queue.offer(node);
        // 加入到队列里面的时候就加入到visitSet里面，方便过滤之后的node
        visitSet.add(node);
        while (!queue.isEmpty()) {
            Node nd = queue.poll();
            System.out.println(nd.value);
            for (Node next : nd.nexts) {
                if (!visitSet.contains(next)) {
                    queue.offer(next);
                    visitSet.add(next);
                }
            }
        }
    }


    /**
     * depth first search
     * @param node
     */
    public static void dfs(Node node) {

        Stack<Node> stack = new Stack<>();
        HashSet<Node> visitSet = new HashSet<>();
        stack.push(node);
        visitSet.add(node);
        while (!stack.isEmpty()) {
            Node visitNode = stack.pop();
            System.out.println(visitNode.value);
            for (int i = visitNode.nexts.size() - 1; i >= 0; i--) {
                Node nd = visitNode.nexts.get(i);
                if (!visitSet.contains(nd)) {
                    stack.push(nd);
                    visitSet.add(nd);
                }
            }
        }
    }

    public static void dfs01(Node node) {

        Stack<Node> stack = new Stack<>();
        stack.push(node);
        HashSet<Node> visitSet = new HashSet<>();
        visitSet.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()) {
            Node visitNode = stack.pop();
            for (Node nextNode : visitNode.nexts) {
                if (!visitSet.contains(nextNode)) {
                    stack.push(visitNode);
                    stack.push(nextNode);
                    visitSet.add(nextNode);
                    System.out.println(nextNode.value);
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {

        Graph graph = createGraph(new Integer[][]{
                {0, 1, 10},
                {0, 2, 4},
                {1, 3, 2},
                {2, 3, 3},
                {3, 1, 3},
                {2, 1, 3}});
        System.out.println(graph);
        Node node = graph.nodes.get(0);
//        bfs(node);
//        dfs(node);
        dfs01(node);
    }
}
